/*
题目: 满足不等式的数对数目
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两个数组的大小都为 n ，同时给你一个整数 diff ，统计满足以下条件的 数对 (i, j) ：

    0 <= i < j <= n - 1 且
    nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.

请你返回满足条件的 数对数目 。

https://leetcode.cn/problems/number-of-pairs-satisfying-inequality
 */
public class NumberOfPairs {
    private long src = 0;
    private int diff = 0;

    public long numberOfPairs(int[] nums1, int[] nums2, int diff) {
        // 归并排序
        // nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff 等效于
        // nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff
        int n = nums1.length;
        this.diff = diff;
        int[] vec = new int[n];
        // 找 vec[i] <= vec[j] + diff
        for (int i = 0; i < n; i ++)
            vec[i] = nums1[i] - nums2[i];

        mergeSort(vec, 0, n - 1);
        return src;
    }

    private void mergeSort(int[] vec, int left, int right) {
        if (left >= right)  return ;

        int mid = left + ((right - left) >> 1);
        mergeSort(vec, left, mid);
        mergeSort(vec, mid + 1, right);

        // core : 在 右侧 数组对于每一个元素 寻找 满足题意的 数对
        for (int b = mid + 1, a = left; b <= right; b ++) {
            while (a <= mid && vec[a] <= vec[b] + diff) {
                a ++;
            }
            // 至此 a ++ , 所以 直接 a - left 即可
            src += a - left;
        }

        merge(vec, left, mid, right);
    }

    private void merge(int[] vec, int start, int mid, int end) {
        int start1 = start, start2 = mid + 1, end1 = mid, end2 = end;
        int[] tmpArr = new int[end - start + 1];
        int k = 0;
        while (start1 <= end1 && start2 <= end2) {
            if (vec[start1] <= vec[start2])
                tmpArr[k ++] = vec[start1 ++];
            else
                tmpArr[k ++] = vec[start2 ++];
        }
        while (start1 <= end1) {
            tmpArr[k ++] = vec[start1 ++];
        }
        while (start2 <= end2) {
            tmpArr[k ++] = vec[start2 ++];
        }

        for (int i = 0; i < k; i ++) {
            vec[start + i] = tmpArr[i];
        }
    }
}
